Năm 1956, khi đơn vị của Nguyễn Văn Đông đang ở Đồng Tháp Mười trong chiến dịch Thoại Ngọc Hầu[lower-alpha 1], dọc theo biên giới Việt Nam - Campuchia. Trên đường về, đơn vị của ông đã gặp một cơn mưa khá lớn, trời chiều gió lộng. Giữa cánh đồng hoang, thoắt ẩn thoắt hiện những nóc tháp canh mờ nhạt ở cuối chân trời. Thế là từ đó, bài hát Chiều mưa biên giới ra đời.

Trong tờ nhạc bướm đã được xuất bản vào năm 1960 do chính tác giả xuất bản, tác giả có đề thêm một dòng giới thiệu như sau[1][2] :

Kính tặng các chiến sĩ một nắng hai sương lao mình nơi tiền tuyến, dâng mình cho đất nước và các bạn thanh niên sắp khoác chiến y. Kỷ niệm Đồng Tháp Mười (Biên giới Viet-Cambod 1956)

— Nguyễn Văn Đông[lower-alpha 2]

Sau bài hát Chiều mưa biên giới, những bài hát Phiên gác đêm xuân, Nhớ một chiều Xuân, Mấy dặm sơn khê, Khúc tình ca hàng hàng lớp lớp lần lượt ra đời.[3]. Tuy nhiên, năm 1961, cả bốn bài hát : Phiên gác đêm xuân, "Mấy dặm sơn khê", "Nhớ một chiều xuân" và "Chiều mưa biên giới" đều bị cấm bởi Bộ Thông tin Việt Nam Cộng hòa, vì có ca từ bị xem là không phù hợp với cuộc chiến, ngoài ra nhạc sĩ Nguyễn Văn Đông bị cấp trên kỷ luật 15 ngày vì câu cuối của bài hát.[4][5]. Cho đến năm 1963, thì việc kiểm duyệt văn hóa nới lỏng hơn, một số bài trên đều được hát trở lại.[5]

Ca khúc nổi tiếng với tiếng hát của ca sĩ Trần Văn Trạch, đã được đài Europe No. 1 và đài Truyền hình Pháp thu âm và thu hình ca khúc, gây tiếng vang lớn trong cộng đồng ở Châu Âu. Nhờ việc này mà chỉ trong vòng 3 tháng, mà nhà xuất bản Tinh Hoa Miền Nam của Lê Mộng Bảo bán được 60 000 tờ nhạc chỉ trong vòng ba tháng, ngoài ra ông còn hát trong đại nhạc hội Trăm Hoa miền Nam của Nguyễn Văn Đông. Sau đó, bài này trở thành một sự kiện âm nhạc lớn vào thời điểm đó.

Sau khi bài hát được lưu hành trở lại vào tháng 11 năm 1963, lúc này kiểm duyệt văn hóa đã được nới lỏng, ca sĩ Hà Thanh cũng đã hát bài này cả trước và sau năm 1975.[6].